๐Ÿ‘ฉโ€๐Ÿ’ป 72411. ๋ฉ”๋‰ด ๋ฆฌ๋‰ด์–ผ

@Seongukbaek Posted June 29, 2022 ยท Updated June 29, 2022 ยท 4 min read

๋ฌธ์ œ

Programmers - ๋ฉ”๋‰ด ๋ฆฌ๋‰ด์–ผ

๐Ÿ“ Logic

// map์— ํ•ด๋‹น ์กฐํ•ฉ์ด ์žˆ๋‹ค๋ฉด, count๋Š” ๊ทธ ์กฐํ•ฉ์˜ ๋นˆ๋„ ์ˆ˜, ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด 0 int count = 0; if (menuComb.containsKey(str)) count = menuComb.get(str); // ํ˜„์žฌ ํ•ด๋‹น ์กฐํ•ฉ์„ ์ถ”๊ฐ€ํ•  ๊ฒƒ์ด๋ฏ€๋กœ count๋ฅผ ์ฆ๊ฐ€ count++; // ํ•ด๋‹น ์กฐํ•ฉ์ด ์ด๋ฏธ ์žˆ์—ˆ๊ณ , ํ•ด๋‹น ์กฐํ•ฉ(๋ฉ”๋‰ด ๊ตฌ์„ฑ)์ด ์†ํ•œ ์ฝ”์Šค ์ค‘ ์ตœ๋Œ€ ๋นˆ๋„๋ณด๋‹ค ๋นˆ๋„๊ฐ€ ํฌ๋‹ค๋ฉด ์ตœ์‹ ํ™” if (count != 1 && courseMaxCount.get(str.length()) < count) courseMaxCount.put(str.length(), count); menuComb.put(str, count);
  • ๋ฉ”๋‰ด ๊ตฌ์„ฑ ๊ธธ์ด๋ณ„ ์ตœ๋Œ€ ๋นˆ๋„์ˆ˜๋ฅผ ์ €์žฅํ•˜๋Š” map ์„ ์ตœ์‹ ํ™”ํ•˜๋Š” ๊ณผ์ •

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Solution { // ๋ชจ๋“  ๋ฉ”๋‰ด ์กฐํ•ฉ์„ ์ €์žฅ static Map<String, Integer> menuComb = new HashMap<>(); // ๊ฐ course๋ณ„ ์ตœ๋Œ€ ๋ฉ”๋‰ด ์ˆ˜๋ฅผ ์ €์žฅ static Map<Integer, Integer> courseMaxCount = new HashMap<>(); // ์ตœ์†Œ ์ฝ”์Šค ์š”๋ฆฌ ์ˆ˜ = course[0] static int minCombCount; public String[] solution(String[] orders, int[] course) { // ๊ฐ ์ฝ”์Šค๋ณ„ ์š”๋ฆฌ ์ˆ˜์— ๋Œ€ํ•œ ์ตœ๋Œ“๊ฐ’์„ ์ €์žฅํ•  map ์ดˆ๊ธฐํ™” for (int c : course) courseMaxCount.put(c, 0); minCombCount = course[0]; // ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ์กฐํ•ฉ์„ ์ƒ์„ฑํ•ด์„œ menuComb์— ์ถ”๊ฐ€ for (String order : orders) { boolean[] visited = new boolean[order.length()]; for (int c : course) if (order.length() >= c) makeComb(order, visited, 0, order.length(), c); } ArrayList<String> answer = new ArrayList<>(); for (Map.Entry<Integer, Integer> entry : courseMaxCount.entrySet()) // ์ตœ๋Œ€ ๋นˆ๋„๋ฅผ ๊ฐ€์ง€๋Š” ๋ฉ”๋‰ด result์— ์ถ”๊ฐ€ for (Map.Entry<String, Integer> menu : menuComb.entrySet()) if (entry.getKey() == menu.getKey().length() && entry.getValue() == menu.getValue()) answer.add(menu.getKey()); Collections.sort(answer); return answer.toArray(String[]::new); } private static void makeComb(String order, boolean[] visited, int start, int n, int r) { // ์ฃผ์–ด์ง„ ์š”๋ฆฌ ์ˆ˜๋งŒํผ์˜ ์กฐํ•ฉ์ด ๋งŒ๋“ค์–ด์ง„ ๊ฒฝ์šฐ, map์— ์ถ”๊ฐ€ if (r == 0) { put(order, visited, n); return; } for (int i = start; i < n; i++) { visited[i] = true; makeComb(order, visited, i + 1, n, r - 1); visited[i] = false; } } private static void put(String order, boolean[] visited, int n) { // Map์— ๋„ฃ์„ ๋ฉ”๋‰ด ์กฐํ•ฉ ์ƒ์„ฑ StringBuilder sb = new StringBuilder(); for (int i = 0; i < order.length(); i++) if (visited[i]) sb.append(order.charAt(i)); // ์ตœ์†Œ ์ฝ”์Šค ์š”๋ฆฌ ์ˆ˜๋ณด๋‹ค ์ž‘์€ ๊ฒฝ์šฐ๋Š” ํŒจ์Šค if (sb.length() < minCombCount) return; // ๋ฉ”๋‰ด ์กฐํ•ฉ ์‚ฌ์ „์ˆœ ์ •๋ ฌ, AB์™€ BA๋Š” ๊ฐ™์€ ๋ฉ”๋‰ด ์กฐํ•ฉ์ด๋ฏ€๋กœ char[] chars = sb.toString().toCharArray(); Arrays.sort(chars); String str = new String(chars); // map์— ํ•ด๋‹น ์กฐํ•ฉ์ด ์žˆ๋‹ค๋ฉด, count๋Š” ๊ทธ ์กฐํ•ฉ์˜ ๋นˆ๋„ ์ˆ˜, ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด 0 int count = 0; if (menuComb.containsKey(str)) count = menuComb.get(str); // ํ˜„์žฌ ํ•ด๋‹น ์กฐํ•ฉ์„ ์ถ”๊ฐ€ํ•  ๊ฒƒ์ด๋ฏ€๋กœ count๋ฅผ ์ฆ๊ฐ€ count++; // ํ•ด๋‹น ์กฐํ•ฉ์ด ์ด๋ฏธ ์žˆ์—ˆ๊ณ , ํ•ด๋‹น ์กฐํ•ฉ(๋ฉ”๋‰ด ๊ตฌ์„ฑ)์ด ์†ํ•œ ์ฝ”์Šค ์ค‘ ์ตœ๋Œ€ ๋นˆ๋„๋ณด๋‹ค ๋นˆ๋„๊ฐ€ ํฌ๋‹ค๋ฉด ์ตœ์‹ ํ™” if (count != 1 && courseMaxCount.get(str.length()) < count) courseMaxCount.put(str.length(), count); menuComb.put(str, count); } }

โœ๏ธ Review

  • ๊ฐ€๋Šฅํ•œ ๋ชจ๋“  ์กฐํ•ฉ์„ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด ๊ฐ€์žฅ ๊ด€๊ฑด์ด์—ˆ๋‹ค. ์ดํ›„ ๊ตฌํ˜„์€ ์ •๋ ฌ์„ ์ž˜ ํ™œ์šฉํ•˜๋ฉด ๋˜๋Š” ๋ฌธ์ œ์˜€๋‹ค.
  • ์ฒ˜์Œ์—๋Š” ์กฐํ•ฉ์„ ๋งŒ๋“ค๊ณ , ๊ฐ ์ฝ”์Šค ์š”๋ฆฌ๋ณ„ ๋ฉ”๋‰ด ์ˆ˜์˜ ์ตœ๋Œ€ ๋นˆ๋„๋ฅผ ๊ตฌํ•˜๊ณ , ๊ทธ ๋นˆ๋„๋ฅผ ๊ฐ€์ง€๋Š” ๋ฉ”๋‰ด ๊ตฌ์„ฑ์„ ์ถœ๋ ฅํ•˜๋„๋ก ํ–ˆ๋‹ค๊ฐ€, ์กฐํ•ฉ์„ ๋งŒ๋“ค๊ณ  map ์— ์ถ”๊ฐ€ํ•  ๋•Œ, ๋ฉ”๋‰ด ๊ตฌ์„ฑ ๊ธธ์ด๋ณ„ ์ตœ๋Œ€ ๋นˆ๋„๋ฅผ ์ €์žฅํ•˜๋Š” map ์„ ๋‘์–ด ์ด๋ฅผ ์‚ฌ์šฉํ•˜๋„๋ก ๋ณ€๊ฒฝํ•ด๋ณด์•˜๋‹ค.
@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€